package _dp_base;

import _object.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 */
public class No124 {
    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftDeepVal = Math.max(dfs(node.left), 0);
        int rightDeepVal = Math.max(dfs(node.right), 0);
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        ans = Math.max(ans, leftDeepVal + rightDeepVal + node.val);
        // 返回节点的最大贡献值
        return Math.max(leftDeepVal, rightDeepVal) + node.val;
    }
}
